/*
 * @lc app=leetcode.cn id=1020 lang=cpp
 *
 * [1020] 飞地的数量
 */

// @lc code=start
typedef pair<int, int> PII;
class Solution
{
    vector<vector<int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

public:
    int numEnclaves(vector<vector<int>> &grid)
    {
        int m = grid.size(), n = grid[0].size();
        deque<PII> q;

        // 将所有的边界上的陆地加入队列
        for (int i = 0; i < m; i++)
        {
            if (grid[i][0] == 1)
            {
                // 标记访问过了
                grid[i][0] = 0;
                q.push_back(PII(i, 0));
            }
            if (grid[i][n - 1] == 1)
            {
                grid[i][n - 1] = 0;
                q.push_back(PII(i, n - 1));
            }
        }
        for (int j = 1; j < n - 1; j++)
        {
            if (grid[0][j] == 1)
            {
                grid[0][j] = 0;
                q.push_back(PII(0, j));
            }
            if (grid[m - 1][j] == 1)
            {
                grid[m - 1][j] = 0;
                q.push_back(PII(m - 1, j));
            }
        }

        while (!q.empty())
        {
            auto [row, col] = q.front();
            q.pop_front();
            // 遍历四个方向
            for (auto dir : dirs)
            {
                int next_row = row + dir[0], next_col = col + dir[1];
                if (next_row < 0 || next_row >= m || next_col < 0 || next_col >= n || grid[next_row][next_col] != 1)
                {
                    continue;
                }
                q.push_back(PII(next_row, next_col));
                grid[next_row][next_col] = 0;
            }
        }

        int ans = 0;
        for (int i = 1; i < m - 1; i++)
        {
            for (int j = 1; j < n - 1; j++)
            {
                if (grid[i][j] == 1)
                {
                    ans++;
                }
            }
        }

        return ans;
    }
};
// @lc code=end
